The present invention relates to a packet switching system having an input buffer and an output buffer (referred to as an input/output buffer packet switching system, hereinafter), particularly to a packet switching system adopting an arbiter system.
A conventional input/output buffer packet switching system, which has a First-In First-Out (FIFO) memory for each input line, has a disadvantage in that, if plural packets inputted from plural input lines converge at a predetermined output path, “Head Of Line (HOL) blocking” is caused, in which there is only 58.6% throughput of data transfer. To avoid HOL blocking, there is provided a well known method in which a Virtual output Queue (VoQ) is provided for each output path at an input buffer.
The input/output buffer packet switching system associated with a crossbar switch, because a crossbar switch has no buffer, adopts a way to arbitrate between the VoQs of input buffers, so as to prevent data on the crossbar switch from being converged. The arbitration is performed for the purpose of selecting a combination of an input port and an output port to which the right of transmitting data (grant) to some of the VoQs is given. Accordingly, higher throughput of data transfer of the switching system depends on efficient arbitration.
There are two ways to effect arbitration for selecting a combination of an input port and an output port: one, where arbitration is performed using the unit of a fixed-length internal packet into which variable length packets inputted to the switch have been divided; and another, where, as indicated in USP Ser. No. 09/362,134, arbitration is performed using the unit of a fixed-length container into which plural variable length packets are packed. In this way, two units are used in the switching processing: one unit in the form of an internal packet having a small fixed length and another unit in the form of a container having a large fixed length.
As regards a unit used in the processing carried out in the switching system of the invention, the volume of data per arbitration is defined as one segment. Note that hereafter the term “segment” is also used as a generic term to indicate data to be treated inside the switch, data such as an internal packet, a packet, and a cell.
As conventional arbitration, the following three methods have been proposed:                First, there is a method of selecting a sending queue on a Round Robin basis by taking into consideration whether a segment of the VoQ exists as a parameter, as disclosed in “A Study of structuring a Large Capacity Packet Switching Systems,” Koji WAKAYAMA, et al., SHINGAKUGIHOU SSE98-160, and also disclosed in JP-A-2000-78148;        Second, there is a method of selecting sending queues by taking the waiting time of the segment in the VoQ as a parameter, as disclosed in “A Study of Scheduling an Input Buffer Switch and Trial manufacture thereof,” Toshiyuki SUDO, et al., SHINGAKUGIHOU SSE99-118; and        Third, there is a method of selecting an output data queue by taking the length of the VoQ as a parameter, as disclosed in “A Proposal of Balanced Packet Scheduling Algorithm and Performance Evaluation,” SHINGAKUGIHOU SSE96-56.        
Each of the three methods has a problem that is caused when an unbalanced load is applied to the switch. Referring to FIG. 16, which is a conceptual view of an input port 30 of a 4×4 switch, an example of the problems will be explained. In the figure, reference numbers 31-1, 31-2, 31-3, and 31-4 denote VoQs, each being directed along its output path; a quadrangle in each VoQ represents a segment. The VoQ 31-1 has traffic which represents a higher load than the other queues; and the VoQ 31-4 has traffic H which represents a lower load than other queues.
In the first method of selecting a sending queue on a Round Robin basis by taking into consideration whether segment of a VoQ exists as a parameter, if unbalanced loads are applied to the switch, the Round Robin approach that equitably reads out segments from all VoQs permits the VoQ having a low load to transmit segments without regard to the VoQ that has a high load and is just reading out a segment. However, the queue of a VoQ having a high load is liable to be long, causing its delay time in segment transmission inside the switch to be longer than those of the other VoQs. As shown in FIG. 16, this brings about an overflow of segments at VoQ 31-1 having a high load, and might result in a segment 32A being abandoned.
In the second method of selecting sending queues by taking the waiting time of a segment in the VoQ as a parameter, in the same way as the first method, the queue of a VoQ having a high load is liable to be long This also causes the waiting time of the segment in a VoQ having a low load to be long, since the method that takes the waiting time of the segment in VoQ as a parameter transmits a segment having a long waiting time in a priority manner. In addition, management of the waiting time of all segments needs a lot of counters, so the method is not practicable.
Therefore, in most cases, the second method counts the waiting time from when the segment has arrived at the top of the queue. Specifically, it adds 1 to the counter of the VoQ when the segment in the VoQ is not transmitted during one arbitration, while it resets the counter when the segment is transmitted during one arbitration. This treats both a VoQ having a high load and a VoQ having a low load in the same way, because the counter resets once the segments of the VoQ which even has a high load are transmitted. Thus, the delay time of the VoQ to which a high load is given under the unbalanced load condition finally becomes large, and thus this might eliminate the overflow segments of the buffer.
In the third method of selecting sending queues by taking the length of the queue as a parameter, the segment can be effectively read out from a VoQ having a high load under above-said condition where an unbalanced load is applied to the switch. Thus, the delay time of the segment of a VoQ having a high load becomes small, also preventing a buffer from overflowing The method, however, suffers from a phenomenon called starvation, in which the grant of a transmission right is not given to a segment 32B of VoQ 31-4 that has a low load.
Accordingly, the method might result in a deterioration of the quality of data in the packets, especially in both packets of voice data, which are required never to be late in data transfer, and packets of important data, which are required never to be abandoned in data transfer, both for keeping good quality in data.